#include "multconjAcotado.h"
#include <cassert>

namespace aed2{

	MultConjAcotado::MultConjAcotado(Nat cota){
		this->repeticiones = new Arreglo<Nat>(cota);
		this->posiciones = new Arreglo<Nat>(cota);
		this->heap = new Arreglo<Nat>(cota);
		this->pos_libre = 0;
		this->cardinal = 0;
		for (Nat i = 0; i < cota; i++){
			this->repeticiones->Definir(i, 0);
			this->posiciones->Definir(i, cota);
		}
	}

	MultConjAcotado::MultConjAcotado(const MultConjAcotado& mconj) {
		repeticiones = new Arreglo<Nat>(*(mconj.repeticiones));
		posiciones = new Arreglo<Nat>(*(mconj.posiciones));
		heap = new Arreglo<Nat>(*(mconj.heap));
		cardinal = mconj.cardinal;
		pos_libre = mconj.pos_libre;
	}

	MultConjAcotado::~MultConjAcotado(){
		delete repeticiones;
		delete posiciones;
		delete heap;
	}

	void MultConjAcotado::Agregar(Nat elemento, Nat cantidad){
		if ((*repeticiones)[elemento] == 0) 
		{
			heap->Definir(pos_libre, elemento);
			posiciones->Definir(elemento, pos_libre);
			pos_libre++;
			repeticiones->Definir(elemento, (*repeticiones)[elemento] + cantidad);
			Subir((*posiciones)[elemento]);
		} else{
			repeticiones->Definir(elemento, (*repeticiones)[elemento] + cantidad);
			Bajar((*posiciones)[elemento]);
		}
		cardinal+= cantidad;
	}

	void MultConjAcotado::Quitar(Nat elemento, Nat cantidad) {

		if (elemento < heap->Tamanho() && (*repeticiones)[elemento]>0){
			if (cantidad <= (*repeticiones)[elemento]){
				cardinal-= cantidad;
				repeticiones->Definir(elemento, (*repeticiones)[elemento] - cantidad);
			} else {
				cardinal-= (*repeticiones)[elemento];
				repeticiones->Definir(elemento, 0);
			}
			Subir((*posiciones)[elemento]);
			/*std::cerr << (*repeticiones) << std::endl;
			std::cerr << (*posiciones) << std::endl;
			std::cerr << (*heap) << std::endl;*/
			if ((*repeticiones)[elemento]==0){
				EliminarRaiz();
			}
		}
	}

	bool MultConjAcotado::Pertenece(Nat elemento) const{
		return repeticiones->Definido(elemento) && (*repeticiones)[elemento] > 0;
	}

	Nat MultConjAcotado::Cardinal() const{
		return cardinal;
	}
	
	Nat MultConjAcotado::Cardinal(Nat elemento) const{
		return (*this->repeticiones)[elemento];
	}

	Nat MultConjAcotado::Minimo() const{
		return (*heap)[0];
	}

	MultConjAcotado::const_Iterador_Unicos MultConjAcotado::Conj() const {
		return const_Iterador_Unicos(this);
	}

	Nat MultConjAcotado::CantDistintos() const{
		return pos_libre;
	}

	//Operaciones auxiliares
	void MultConjAcotado::EliminarRaiz(){
		if (CantDistintos() > 1) {
			heap->Definir(0, (*heap)[pos_libre - 1]);
			pos_libre--;
			posiciones->Definir(pos_libre, heap->Tamanho());
			Bajar(0);
		} else {
			pos_libre--;
			posiciones->Definir(pos_libre, heap->Tamanho());
		}

	}

	void MultConjAcotado::Subir(Nat pos){
		Nat i = pos;
		while ((i != 0) && Prioridad((*heap)[i]) < Prioridad((*heap)[Padre(i)])){
			Nat p = Padre(i);
			IntercambiarPosiciones(i,p);
			i = p;
		}
	}

	Nat MultConjAcotado::Prioridad(Nat elemento) const{
		return ((*repeticiones)[elemento] + 1) * heap->Tamanho() - elemento;
	}

	Nat MultConjAcotado::Padre(Nat i) const{
		return (i - 1) / 2;
	}

	void MultConjAcotado::Bajar(Nat pos){
		Nat i = pos;
		Nat izq = 2 * i + 1;
		Nat der = 2 * i + 2;
		while ((i < pos_libre / 2) && ((izq < pos_libre && Prioridad(i) > Prioridad(izq)) || (der < pos_libre && Prioridad(i) > Prioridad(der)))){
			Nat h;
			if (Prioridad(izq) < Prioridad(der))
				h = izq;
			else
				h = der;
			IntercambiarPosiciones(i,h);
			i=h;
			izq = 2 * i + 1;
			der = 2 * i + 2;
		}
	}

	void MultConjAcotado::IntercambiarPosiciones(Nat i, Nat j){
		Nat valorI = (*heap)[i];
		Nat valorJ = (*heap)[j];

		Nat posI = (*posiciones)[valorI];
		Nat posJ = (*posiciones)[valorJ];

		//intercambio posiciones
		posiciones->Definir(valorI, posJ);
		posiciones->Definir(valorJ, posI);

		//intercambio valores en el heap
		heap->Definir(i, valorJ);
		heap->Definir(j, valorI);
	}

    /*****************************************************************************/
    /**************************** const_Iterador ******************************/
    /*****************************************************************************/

	/**
     * Crea un iterador bidireccional del conjunto, de forma tal que HayAnterior
     * evalúe a false (i.e., que se pueda recorrer los elementos aplicando
     * iterativamente Siguiente). Este iterador no permite modificar el conjunto.
     * Implementa la función CrearIt(in c: conjAcotado) -> res : itConj
     * PRE: { true }
     * POS: { esPermutación?(SecySuby(res), ConjSuby(c)) ^ vacia?(Anteriores(res)) }
     * Complejidad: O(1)
     */
    MultConjAcotado::const_Iterador MultConjAcotado::CrearIt() const{
		return const_Iterador(this);
	}
		
    /**
     * Crea un iterador bidireccional del conjunto, de forma tal que HayAnterior
     * evalúe a false (i.e., que se pueda recorrer los elementos aplicando
     * iterativamente Siguiente). Este iterador no permite modificar el conjunto.
     * Implementa la función CrearIt(in c: conjAcotado) -> res : itConj
     * PRE: { true }
     * POS: { esPermutación?(SecySuby(res), ConjSuby(c)) ^ vacia?(Anteriores(res)) }
     * Complejidad: O(1)
     */
    MultConjAcotado::const_Iterador::const_Iterador(const MultConjAcotado* conjunto) : 
        conj(conjunto), pos(0) {}

    /**
     * Devuelve true si en el iterador todavía quedan elementos por avanzar.
     * Implementa la función HAYSIGUIENTE(in it: itConj) -> res : bool
     * PRE: { true }
     * POS: { res = haySiguiente?(it) }
     * Complejidad: O(1)
     */
    bool MultConjAcotado::const_Iterador::HaySiguiente() const {
        return pos < conj->pos_libre;
    }

    /**
     * Devuelve true si en el iterador todavía quedan elementos por retroceder.
     * Implementa la función HAYANTERIOR(in it: itConj) -> res : bool
     * PRE: { true }
     * POS: { res = hayAnterior?(it) }
     * Complejidad: O(1)
     */
    bool MultConjAcotado::const_Iterador::HayAnterior() const {
        return pos > 0;
    }

    /**
     * Devuelve el elemento siguiente a la posición del iterador.
     * Implementa la función SIGUIENTE(in it: itConj) -> res : nat
     * PRE: { HaySiguiente?(it) }
     * POS: { res = Siguiente(it) }
     * Complejidad: O(1)
     */
    Nat MultConjAcotado::const_Iterador::Siguiente() const {
        assert(HaySiguiente());
        return (*conj->heap)[pos];
    }
    
    /**
     * Devuelve el elemento siguiente a la posición del iterador.
     * Implementa la función SIGUIENTE(in it: itConj) -> res : nat
     * PRE: { HaySiguiente?(it) }
     * POS: { res = Siguiente(it) }
     * Complejidad: O(1)
     */
    Nat MultConjAcotado::const_Iterador::CardinalSiguiente() const {
        assert(HaySiguiente());
        return (*conj->repeticiones)[(*conj->heap)[pos]];
    }

    /**
     * Devuelve el elemento anterior a la posición del iterador.
     * Implementa la función ANTERIOR(in it: itConj) -> res : nat
     * PRE: { HayAnterior?(it) }
     * POS: { res = Anterior(it) }
     * Complejidad: O(1)
     */
    Nat MultConjAcotado::const_Iterador::Anterior() const {
        assert(HayAnterior());
        return (*conj->heap)[pos-1];
    }

    /**
     * Devuelve el elemento anterior a la posición del iterador.
     * Implementa la función ANTERIOR(in it: itConj) -> res : nat
     * PRE: { HayAnterior?(it) }
     * POS: { res = Anterior(it) }
     * Complejidad: O(1)
     */
    Nat MultConjAcotado::const_Iterador::CardinalAnterior() const {
        assert(HayAnterior());
        return (*conj->repeticiones)[(*conj->heap)[pos - 1]];
    }
    
    /**
     * Avanza a la posición siguiente del iterador.
     * Implementa la función AVANZAR(in/out it: itConj)
     * PRE: { it = it_0 ^ HaySiguiente?(it) }
     * POS: { it = Avanzar(it_0) }
     * Complejidad: O(1)
     */
    void MultConjAcotado::const_Iterador::Avanzar() {
        assert(HaySiguiente());
        pos++;
    }

    /**
     * Retrocede a la posición anterior del iterador.
     * Implementa la función RETROCEDER(in/out it: itConj)
     * PRE: { it = it_0 ^ HayAnterior?(it) }
     * POS: { it = Retroceder(it_0) }
     * Complejidad: O(1)
     */
    void MultConjAcotado::const_Iterador::Retroceder() {
        assert(HayAnterior());
        pos--;
    }

	/**
	 * Genera una representación del multiconjunto con un string y la escribe dentro
	 * de un output stream.
	 */
	std::ostream& operator<<(std::ostream& os, const MultConjAcotado& mc) {
		MultConjAcotado::const_Iterador it = mc.CrearIt();
		os << '{';
        while(it.HaySiguiente()) {
            os << it.Siguiente();
            for (Nat i = 0; i < it.CardinalSiguiente() - 1; i++){
				os << ',';
				os << it.Siguiente();
			}
            it.Avanzar();
            if(it.HaySiguiente()) os << ',';
        }
        return os << '}';
	}

}
